//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返
//回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 
//
// 
//
// 示例 1： 
//
// 
//输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出：[[1,6],[8,10],[15,18]]
//解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 
//
// 示例 2： 
//
// 
//输入：intervals = [[1,4],[4,5]]
//输出：[[1,5]]
//解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 
//
// 
//
// 提示： 
//
// 
// 1 <= intervals.length <= 104 
// intervals[i].length == 2 
// 0 <= starti <= endi <= 104 
// 
// Related Topics 数组 排序 
// 👍 1018 👎 0


package service.week05.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java：合并区间
public class P56MergeIntervals{
    public static void main(String[] args) {
        Solution solution = new P56MergeIntervals().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 双关键字排序
         * @param intervals
         * @return
         */
    public int[][] merge(int[][] intervals) {
        //先将数组排序
        Arrays.sort(intervals,(a,b)->{
           if ((a[0]<b[0]) || (a[0]==b[0] && a[1]>b[1])){
               return -1;
            }else{
               return 1;
            }
        });
        int left=-1;
        int far=-1;
        List<List> resList=new ArrayList<>();
        for(int[] vals:intervals){
            int start =vals[0];
            int end =vals[1];
            if(start<=far){
                //延续
                far=Math.max(far,end);
            }else {
                //旧答案放入list
                if(far>0){
                    resList.add(Arrays.asList(left,far));
                }
                //新起一段
                left=start;
                far=end;
            }
        }
        //转换成数组
        int[][] res=new int[resList.size()][resList.get(0).size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i][0]=(Integer) resList.get(i).get(0);
            res[i][1]=(Integer) resList.get(i).get(1);
        }
        return res;
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}